/**
    ******************************************************************************
    * @file    biTree.c
    * @author  debian
    * @version V1.0.0
    * @date    2019-12-08
    * @brief   二叉树
    ******************************************************************************
    * @attention
    *
    *
    ******************************************************************************
    */ 

/* Includes ------------------------------------------------------------------*/
#include "biTree.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

/** @addtogroup DataStruct_Driver
    * @{
    */

/** @addtogroup biTree
    * @{
    */

/* Private typedef -----------------------------------------------------------*/

/* Private define ------------------------------------------------------------*/

/* Private macro -------------------------------------------------------------*/

/* Private variables ---------------------------------------------------------*/

/* Private function prototypes -----------------------------------------------*/

/* Private functions ---------------------------------------------------------*/


/** @defgroup biTree_Exported_Functions biTree Exported Functions
    * @{
    */

/** @defgroup biTree_Exported_Functions_Group1 Initialization and deinitialization functions
    *  @brief    Initialization and Configuration functions
    *
@verbatim    
    ===============================================================================
                ##### Initialization and deinitialization functions #####
    ===============================================================================
    [..]
        This section provides functions allowing to initialize and de-initialize the biTree
        to be ready for use.
 
@endverbatim
    * @{
    */ 

/**
    * @brief  创建biTree对象
    * @param  	
    * @retval 
    */ 
    int biTree_creat(void)
    {	
        return 0;
    }

/**
    * @brief  销毁biTree对象
    * @param  
    * @retval 
    */ 
    int biTree_destroy(void)
    {
        return 0;
    }
    
/**
    * @}
    */

/** @defgroup biTree_Exported_Functions_Group2 operation functions 
    *  @brief   operation functions
    *
@verbatim   
    ===============================================================================
                        ##### operation functions #####
    ===============================================================================
    [..]
        This subsection provides a set of functions allowing to manage the biTree.

@endverbatim
    * @{
    */

	/**
		* @brief  创建新结点
		* @param	
		* @retval 
		*/ 
		struct BiTree_node *biTree_creat_node(Elemtype data)
		{	
			struct BiTree_node *node = (struct BiTree_node*)malloc(sizeof(struct BiTree_node));
			assert(node);

			node->data = data;
			node->bst.left = NULL;
			node->bst.right = NULL;

			return node;
		}


	
	/**
		* @brief  插入二叉树对象（包括根结点）
		* @param	
		* @retval 
		*/ 
		int biTree_insert(struct BiTree *T, Elemtype data)
		{	
			assert(T);

			//如果头节点为空，就创建头结点
			if(T->root == NULL){
				T->root = biTree_creat_node(data);
				return 0;
			}

			//1.判断插入点
			struct BiTree_node *node = T->root;
			struct BiTree_node *temp = T->root;
			while(node != NULL){
				//记录上一个结点指针，这个跟单链表的插入有点像
				temp = node;
				//data比根结点小，往左子树走
				if(node->data > data){
					node = node->bst.left;
				}else {  //否则往右子树走
					node = node->bst.right;
				}				
			}

			//判断要插入的是左子树还是右子树
			if(temp->data > data){
				temp->bst.left = biTree_creat_node(data);	
			}else {
				temp->bst.right = biTree_creat_node(data);
			}	

			return 0;
		}


	/**
		* @brief  删除二叉树结点
		* @param	
		* @retval 
		*/ 
		static int biTree_deleteNode(struct BiTree_node *node, struct BiTree_node *prev_node)
		{	
			struct BiTree_node *q, *s;
			//只有右子树，需要接左子树
			if(node->bst.left == NULL)  {
				prev_node->bst.right = node->bst.right;
				free(node);
			}else if(node->bst.right == NULL)  {   //只有右子树,只接右子树
				prev_node->bst.left = node->bst.left;
				free(node);
			}else {		
				//左右子树都存在，直接寻找要删除结点的直接前继
				//直接前继就是node结点的左子树的最后边的数据
				s = node->bst.left;
				q = node;
				while(s->bst.right)
				{
					q = s;s = s->bst.right;		//寻找最右边的结点，还要考虑这个结点是否有左子树
				}
				
				//q要保存，这是s的父结点，s的左子树要挂在到q这个结点上
				if(q == node)  //相等的话，就是s=node左子树，已经是直接后继了
				{
					//不改变
				}
				else		//不想等的话，说明node的左子树是有右子树的，q是s的父节点，s是q的右子树，s的左子树要挂在q的右子树上
				{		
					q->bst.right = s->bst.left;
					s->bst.left = node->bst.left;
				}

				//把s挂在prev_node的上，不过需要判断是左子树还是右子树
				if(prev_node->data > s->data)   //左子树
				{
					prev_node->bst.left = s;
				}
				else
				{
					prev_node->bst.right = s;
				}
				s->bst.right = node->bst.right;
				free(node);
			}

			return 0;
		}
	


	/**
		* @brief  查找二叉树数据
		* @param	
		* @retval 
		*/ 
		int biTree_delete(struct BiTree *T, Elemtype data)
		{	
			struct BiTree_node *node = T->root;
			struct BiTree_node *temp = T->root;

			while(node)
			{
				if(node->data == data){
					//要删除的结点
					biTree_deleteNode(node, temp);
				}
				else if(node->data > data) {   //往左子树走
					temp = node;
					node = node->bst.left;
				}
				else  {
					temp = node;
					node = node->bst.right;
				}
			}

			return 0;
		}

	/**
		* @brief  查找二叉树数据
		* @param	
		* @retval 
		*/ 
		int biTree_search(struct BiTree_node* node, Elemtype data)
		{	
			if(node == NULL)						//说明找不到结点
				return -1;

			if(node->data == data)  {				//递归的返回条件
				printf("biTree_search %d\n", data);
				return 0;
			}
			else if(node->data > data){				//往左子树
				biTree_search(node->bst.left, data);
			}
			else{
				biTree_search(node->bst.right, data);
			}

			return 0;
		}
	

		
		/**
			* @brief  前序遍历,先遍历根结点，再左子树，然后右子树
			* @param	
			* @retval 
			*/ 
			void bstree_preOrderTraversal(struct BiTree_node* node)
			{	
				if(node == NULL)
					return ;

				printf("%d ", node->data);
				bstree_preOrderTraversal(node->bst.left);
				bstree_preOrderTraversal(node->bst.right);	
			}

		/**
			* @brief  中序遍历,先左子树，再根结点，然后右子树
			* @param	
			* @retval 
			*/ 
			void bstree_iNOrderTraversal(struct BiTree_node* node)
			{	
				if(node == NULL)
					return ;

				bstree_iNOrderTraversal(node->bst.left);
				printf("%d ", node->data);
				bstree_iNOrderTraversal(node->bst.right);	
			}

		/**
			* @brief  后序遍历,先左子树，再右子树，然后根结点
			* @param	
			* @retval 
			*/ 
			void bstree_postOrderTraversal(struct BiTree_node* node)
			{	
				if(node == NULL)
					return ;

				bstree_postOrderTraversal(node->bst.left);
				
				bstree_postOrderTraversal(node->bst.right);	
				printf("%d ", node->data);
			}


		#if 1
		int main()
		{
			int i = 0;
			int ret = -1;
			int aa[] = {12, 45, 89, 124, 7, 4, 56, 54, 789, 9};
	
			struct BiTree T = {0}; 		//二叉树头结点

			//二叉树是左结点比双亲结点小，右结点比双亲结点大
			for(i=0; i<10; i++)
			{
				biTree_insert(&T, aa[i]);
			}

			//前序遍历二叉树
			bstree_preOrderTraversal(T.root);
			printf("\n");
			bstree_iNOrderTraversal(T.root);
			printf("\n");
			bstree_postOrderTraversal(T.root);
			printf("\n");

			biTree_search(T.root, 124);

			biTree_delete(&T, 89);
			
			//biTree_insert(&T, 567);
			bstree_preOrderTraversal(T.root);
			printf("\n");
			
			return 0;
	
		}
	#endif

    /**
    * @}
    */


/**
    * @}
    */

/**
    * @}
    */

/**
    * @}
    */

/************************ (C) 2019 HOME 深圳龙华 *****END OF FILE****/

